CF439E Devu and Birthday Celebration

$\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1]$

$\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d)$

$\sum_{d|n} \mu(d) \sum_{i_1=1}^{\frac{n}{d}}\sum_{i_2=1}^{\frac{n}{d} }...\sum_{i_f=1}^{\frac{n}{d}} [\sum{a_i}=\frac{n}{d}]$

后面枚举 $i$ 的过程可以看作将 $\frac{n}{d}$ 个相同的球放进 $f$ 个不同的盒子，且不能有空盒的方案数，利用插板法可得： $\binom{\frac{n}{d}-1}{f-1}$

那么原式即为：

$\sum_{d|n} \mu(d) \binom{\frac{n}{d} - 1 }{f-1}$

#include <cstdio>

const int MAXN = 1e5 , Mod = 1e9 + 7;

int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = 1ll * x * x % Mod ) if( po & 1 ) p = 1ll * p * x % Mod; return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ prnum ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= prnum && i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}
int fac[ MAXN + 5 ] , ivf[ MAXN + 5 ];
void Init( ) {
	fac[ 0 ] = 1;
	for( int i = 1 ; i <= MAXN ; i ++ ) fac[ i ] = 1ll * fac[ i - 1 ] * i % Mod;
	ivf[ MAXN ] = Inv( fac[ MAXN ] );
	for( int i = MAXN ; i >= 1 ; i -- ) ivf[ i - 1 ] = 1ll * ivf[ i ] * i % Mod;
}
int C( int n , int m ) {
	return n < m ? 0 : 1ll * fac[ n ] * ivf[ m ] % Mod * ivf[ n - m ] % Mod;
}


int Solve( int n , int f ) {
	int Ans = 0;
	for( int d = 1 ; d * d <= n ; d ++ )
		if( n % d == 0 ) {
			Ans = ( Ans + mu[ d ] * C( n / d - 1 , f - 1 ) ) % Mod;
			if( d * d != n ) Ans = ( Ans + mu[ n / d ] * C( d - 1 , f - 1 ) ) % Mod;
		}
	return ( Ans + Mod ) % Mod;
}

int q , n , f;
int main( ) {
	Init(); sieve();
	scanf("%d",&q);
	while( q -- ) {
		scanf("%d %d",&n,&f);
		printf("%d\n", Solve( n , f ) );
	}
	return 0;
}